#ifndef OCTREE_DEF_H
#define OCTREE_DEF_H

#include <array.hpp>

#include "Vector3.hpp"

/**
 * @brief  Octree 简单实现八叉树
 * x 左右 y 前后 z上下
 * Octree 构建过程：
 * 1. 为当前最大空间建立一个立方体
 * 2. 如果立方体中 存在多个点时，需要拆分8等分的子立方体，再将点塞入子节点中（需要清空父节点 存储的点）
 * 3. 重复上一步操作直到，所有点都插入到Octree 中
 * Octree 满足特性：
 * 1. 只有叶子节点存储实际数据是有效的
 * 2. 一个节点对应一个立方体，包含的点是 所有子节点点之和
 */

/**
 * @brief EBoxPos  两点基于立方体内的方位
 */
enum class EBoxPos {
    LeftBackDown = 0, // 左后下
    LeftBackUp,
    LeftFrontDown,
    LeftFrontUp,
    RightBackDown,
    RightBackUp,
    RightFrontDown,
    RightFrontUp,
};

/**
 * 0b000 三位二进制数 xyz 可以标记 EBoxPos
 * 1 标记为正区间，0 标记负数区间， 如果相同算正区间的
 */
static const int BOX_POS_X_MASK = 0b100;
static const int BOX_POS_Y_MASK = 0b010;
static const int BOX_POS_Z_MASK = 0b001;

using Vec3 = Vector3<float>;

class Octree {
private:
    Vec3 _origin;                     // 原点
    Vec3 _radius;                     // 立方体范围
    Vec3 *_data = nullptr;            // 存储的点 ！！！不会copy 数据，只有持有元数据的引用
    Octree *_children[8] = {nullptr}; // 子节点， EBoxPos 每一个值对应子节点

public:
    Octree(Octree &&other);
    ~Octree();
    // 创建一个空的八叉树
    static Octree buildOctree(const Vec3 &origin, const Vec3 &radius, const TingSTL::array<Vec3> &points);

    // 是否为叶子节点
    inline bool isLeafNode() const {
        return _children[0] == nullptr;
    }

    // 判断所在区域是否完全在 范围的外
    bool isOutBox(const Vec3 &bmin, const Vec3 &bmax) const;

    // 插入数据
    void insert(Vec3 *data);

    // 获取范围内的点
    TingSTL::array<Vec3 *> getPointsInsideBox(const Vec3 &bmin, const Vec3 &bmax) const;

private:
    Octree(const Vec3 &origin, const Vec3 &radius); // 不允许外部构造

    // 获取 pos 在当前立方体所在的方位
    EBoxPos getBoxPos(const Vec3 &pos) const;
    // 构建子树
    void buildChildren();

    void _getPointsInsideBox(const Vec3 &bmin, const Vec3 &bmax, TingSTL::array<Vec3 *> &points) const;
};

#endif // OCTREE_DEF_H
